package tree

import "math"

//给定一个二叉树，找出其最小深度。
//最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
//说明：叶子节点是指没有子节点的节点

//方法1：深度优先搜寻
func MinDepthDFS(root *Node) int {
	if root == nil {
		return 0
	}
	if root.Left == nil && root.Right == nil {
		return 1
	}
	min := math.MaxInt32 //中间变量
	if root.Left != nil {
		min = int(math.Min(float64(MinDepthDFS(root.Left)), float64(min)))
	}
	if root.Right != nil {
		min = int(math.Min(float64(MinDepthDFS(root.Right)), float64(min)))
	}
	return min + 1
}

func MinDepthBFS(root *Node) int {
	if root == nil {
		return 0
	}
	queue := []*Node{}
	count := []int{}
	queue = append(queue, root)
	count = append(count, 1)
	for i := 0; i < len(queue); i++ {
		node := queue[i]
		depth := count[i]

		if node.Left == nil && node.Right == nil {
			return depth
		}

		if node.Left != nil {
			queue = append(queue, node.Left)
			count = append(count, depth+1)
		}

		if node.Right != nil {
			queue = append(queue, node.Right)
			count = append(count, depth+1)
		}
	}
	return 0
}
